public class Leetcode1780 {
    public static void main(String[] args) {
        System.out.println(2 << 15);
    }

    public boolean checkPowersOfThree(int n) {
        if (n == 1) {
            return true;
        }

        if (n % 3 == 0) {
            return checkPowersOfThree(n / 3);
        }

        if ((n - 1) % 3 == 0) {
            return checkPowersOfThree((n - 1) / 3);
        }

        return false;
    }

    public boolean checkPowersOfThree1(int n) {
        return Integer.toString(n, 3).contains("2");
    }

    int[] number = new int[]{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969};

    public boolean checkPowersOfThree2(int n) {
        int length = number.length;
        int all = 2 << length;
        for (int i = 0; i < all; i++) {
            int res = 0;
            for (int j = 0; j < length; j++) {
                if ((i & 1 << j) != 0) {
                    res += number[j];
                }
            }

            if (res == n) {
                return true;
            }

            if (res > n) {
                return false;
            }
        }

        return false;
    }


}
